package hot_100;

/**
 * @author: Darven
 * @createTime: 2025-10-02  11:55
 * @description: TODO
 */
public class P25 {

    public static void main(String[] args) {
        ListNode head=new ListNode(0);
        ListNode cur=head;
        for(int i=1;i<=5;i++){
            cur.next=new ListNode(i);
            cur=cur.next;
        }
        head=head.next;
        P25 p25 = new P25();
        ListNode node = p25.reverseKGroup(head, 3);
        while (node!=null){
            System.out.println(node.val);
            node=node.next;
        }
    }


    public ListNode reverseKGroup(ListNode head, int k) {
        /**
         * 先拆分，然后按照区间进行反转链表
         * */

        if(head==null||head.next==null){
            return head;
        }

        ListNode dummy=new ListNode(-1);
        ListNode pre=dummy;
        // 操作head
        ListNode start=head;
        ListNode end=head;

        while(end!=null){
            // 找到end边界，如果end为空就直接退出
            for(int i=1;i<k&&end!=null;i++){
                end=end.next;
            }
            if(end==null){
                break;
            }
            // 指向下一个
            ListNode next =end.next;
            // 截断区间
            end.next=null;
            // 区间反转
            pre.next=reverse(start);
            // 反转之后start变成最后一个
            pre=start;
            start=next;
            end=next;
        }
        // 接上start，避免没有倍数的部分
        pre.next=start;
        return dummy.next;
    }

    // 头插法
    private ListNode reverse(ListNode start) {
        ListNode pre=null;
        ListNode cur=start;

        while (cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }

        return pre;
    }
}
